package com.yb.chapter1;

import java.util.Stack;

/**
 * 描述：递归操作逆序一个栈的数据
 * 要求：压栈  1,2,3,4,5 从栈顶到栈底依次是  5,4,3,2,1 ，
 *      采用递归将栈数据从栈顶到栈底的数据 1,2,3,4,5
 * 思路：递归就是一个栈数据结构，一个递归就是一次入栈出栈操作，所以一次的递归肯定是不行的，需要多次的递归嵌套
 * @author yb
 * @date 2021/12/24 16:01
 */
public class RecursionStack {

    private Stack<Integer> stack;

    public RecursionStack(){
        this.stack = new Stack<Integer>();
    }

    public Stack<Integer> getStack() {
        return stack;
    }

    public Integer push(Integer data){
        return this.stack.push(data);
    }

    public static void flipStack(Stack<Integer> stack){

        if(stack.isEmpty()){
            return;
        }
        Integer i = getStackBottomAndRemove(stack);
        flipStack(stack);
        stack.push(i);
    }


    public static Integer getStackBottomAndRemove(Stack<Integer> stack){
        //先弹出一个栈顶元素
        int result = stack.pop();
        //已经是栈底的一个元素，则返回
        if(stack.isEmpty()){
            return result;
        }else{
            Integer last = getStackBottomAndRemove(stack);
            stack.push(result);
            return last;
        }
    }



    public void printAndClearStack(){
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+"  ");
        }
    }


    public static void main(String[] args) {
        RecursionStack stack = new RecursionStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
//        System.out.println("转换前从栈顶到栈底依次是===========");
//        stack.printAndClearStack();
        System.out.println("转换后从栈顶到栈底依次是===========");
        RecursionStack.flipStack(stack.getStack());
        stack.printAndClearStack();

    }

}
